|
|
Reading Group on Algorithmic Techniques |
Summary: In this reading group we try to understand recent useful algorithmic techniques, and their connections to various other areas such as computational complexity, combinatorial and polynomial optimization, quantum computing and so on.
We usually meet at Klaus Advanced Computing Building (KACB 2100, MonDay 15:00, but this may change depending
on availability of people).
The exact time and location for each lecture will be posted below. The
table below also has relevant reading material/slides for each lecture.
Below is also a tentative list of possibly interesting papers to present. If you would like to present one of the papers, or add some to this list, please let Arindam know (email: arindamkhan [at] gatech.edu).
Some Tentative Topics: Iterative Methods, Lovasz Local Lemma, LP/SDP Hierarchies, Submodular Optimization, Dependent Rounding, Discrepancy/Entropy based Rounding, Epsilon Nets, Parameterized Complexity, Other recent interesting papers in STOC/FOCS/SODA.
Please feel free to suggest any other useful interesting topic/paper.
Lectures:
| Date/Time | Title | Reading Material | |
| 1 | Nov 3, Mon 15:00 (Klaus, room 2100) | Introduction to Iterative methods. Speaker: Arindam Notes on Matching, Spanning Tree. | We will follow chapter 1 and 3 from Lau-Ravi-Singh's boook:
Iterative Methods in Combinatorial Optimization (pdf) We will show integrality of bipartite matching LP and an approximation of Generalized Assignment problem [Shmoys-Tardos] using Iterative methods. |
| 2 | Nov 10, Mon 15:00 (Klaus, room 2100) |
Iterative Methods and Spanning Trees. Speaker: Arindam |
We will follow chapter 4 from Lau-Ravi-Singh's boook:
Iterative Methods in Combinatorial Optimization (pdf) We will cover integrality of subtour LP for spanning trees. Introduce iterative leaf-finding, 1-edge finding algorithm and global counting, local token counting arguments. We will see applications of uncrossing arguments and rank lemma. We will then study minimum degree bounded spanning trees. First Goemans' result where degree bound is violated by an additive factor of 2 [FOCS 06] and then additive violation of 1 by Singh-Lau [STOC 07]. |
| 3 | Nov 17, Mon 15:30 (Klaus, room 2100) |
Dual Fitting. Speaker: Ruta |
Greedy facility location algorithms analyzed using dual fitting with factor-revealing {LP} by Jain et al.(pdf)
We will study the use of Factor Revealing LP, Dual Fitting and a brief survey on uncapacitated facility location problem. |
| 4 | Nov 24, Mon 15:00 (Klaus, room 2100) |
Constructive Proof of Lovasz Local Lemma. Speaker: Bartosz |
We will study Moser Tardos Framework for constructive proof of Lovasz Local Lemma (pdf) |
| 5 | Dec 3, Wed 13:00 (Klaus, room 2108) |
Lovasz Local Lemma and Partial Resampling. Speaker: Ioannis |
We will study Moser Tardos Framework with Partial Resampling by Harris and Srinivasan. (pdf) |
| 6 | March 9, Mon 17:00 (Klaus, room 2119) |
Online Algorithms. Speaker: Arindam |
We will study basics of Online Algorithms such as competitive ratios and use of potential functions in the analysis. 1. Load Balancing Algorithm by Aspnes et al. (pdf) 2. Multiplicative Weight Updates by Arora Hazan Kale (pdf) |
| 7 | March 30, Mon 16:00 (Klaus, room 2108) |
Fixed Parameter Tractability. Speaker: Bartosz |
We will study basics of Fixed parameter Tractability such as kernelization, bounded search tree, iterative compression, graph minors and color coding. Daniel Marx's slides on Fixed Parameter Algorithms: Part 1: Algorithmic techniques, Part 2: Treewidth, Part 3: Complexity |
| 8 | April 6, Mon 16:00 (Klaus, room 2108) |
Fixed Parameter Tractability. Speaker: Bartosz |
We continue discussions on Fixed parameter Tractability with focus on iterative compression, tree width, excluded grid theorem and irrelevant vertex techniques for k-planarity deletion and k-odd cycle transversal problem. Daniel Marx's slides on Fixed Parameter Algorithms: Part 1: Algorithmic techniques, Part 2: Treewidth, Part 3: Complexity |
List of Papers (with links):